/**
 * 668. 乘法表中第k小的数
 * https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/
 */
public class Solutions_668 {
    public static void main(String[] args) {
//        int m = 3, n = 3, k = 5;  // output: 3
//        int m = 3, n = 3, k = 8;  // output: 6
        int m = 3, n = 3, k = 6;  // output: 4
//        int m = 2, n = 3, k = 6;  // output: 6

        int result = findKthNumber(m, n, k);
        System.out.println(result);
    }

    /**
     * 不用担心最终结果不在矩阵中
     * 因为 cnt >= k 时，使 right = mid，即 mid 会越来越小
     * 比如 6 和 7，8 都满足条件，6 在矩阵中，而 7，8 没有在矩阵中
     * 最终结果是 6
     */
    public static int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int cnt = check(m, n, mid);
            // 若矩阵中有 9 个元素，要求出第 1 小的元素，即矩阵中要有 1 个元素小于等于 mid
            if (cnt >= k) {
                // 说明 mid 还可以再小，即 right 缩小
                right = mid;
            } else {
                // 说明 mid 过小，还可以再大，即 left 扩大
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 计算出矩阵中有多少个元素小于等于 mid
     */
    public static int check(int row, int col, int num) {
        int i = row - 1, j = 0;
        int cnt = 0;
        while (i >= 0 && j < col) {
            if (num >= (i + 1) * (j + 1)) {
                // 该列上，有 i + 1 个数小于等于 num
                cnt += i + 1;
                j ++;
            } else {
                i --;
            }
        }
        return cnt;
    }
}
